package com.bo.day20241121;

import java.util.*;

/**
 * 拓扑排序
 * 原理：有向无环图，从入度为0的点开始，每次出队一个点，然后遍历该点的所有出边，将出边指向的点的入度减1，如果入度减为0，则入队。
 *
 * @Author: gpb
 * @Date: 2024/11/27 14:58
 * @Description:
 */
public class TopologySort {
    public static List<Node> topoSort (Graph graph) {
        // 创建一个map, key为节点，value为该节点的入度
        Map<Node, Integer> inMap = new HashMap<>();
        // 创建一个队列，用于存储入度为0的节点
        Queue<Node> zeroInQueue = new LinkedList<>();
        for (Node value : graph.nodes.values()) {
            // 记录每个节点的入度
            inMap.put(value, value.in);
            if (value.in == 0) {
                // 入度为0的节点入队
                zeroInQueue.add(value);
            }
        }
        // 拓扑排序结果
        List<Node> result = new ArrayList<>();
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            result.add(cur);
            // 弹出的节点,对应的节点入度减法-1
            for (Node next : cur.nexts) {
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    // 入度为0的节点入队
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}
